/*
题目: 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串
https://leetcode.cn/problems/palindrome-partitioning/
 */
public class MinCut {
    List<List<String>> src = new ArrayList<> ();
    List<String> path = new ArrayList<> ();

    public List<List<String>> partition(String s) {
        // 预处理+动归+回溯
        int n = s.length();

        boolean[][] isPalind = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalind[i][i] = true;

        // 预处理所有回文串
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j ++) {
                isPalind[j][i] = (s.charAt(i) == s.charAt(j)) && (i - j == 1 || isPalind[j + 1][i - 1]);
            }
        }
        backTrack(s, isPalind, 0, n);
        return src;
    }

    private void backTrack(String s, boolean[][] isPalind, int start, int end) {
        if (start >= end) {
            src.add(new ArrayList<> (path));
            return ;
        }

        for (int i = start; i < end; i++) {
            if (isPalind[start][i]) { // [start, i] 是回文串
                path.add(s.substring(start, i + 1));
                backTrack(s, isPalind, i + 1, end);
                path.remove(path.size() - 1);
            }
        }
    }
}
